package 代码记录.Bit48天集训;

import java.util.Scanner;

/**1.字符串计数(此题在牛客上找不到练习题)
 * 2.最长公共子序列
 * @author zx
 * @create 2022-06-29 16:59
 */
public class day_39 {
    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s1 = sc.next();
            String s2 = sc.next();
            int len1 = sc.nextInt();
            int len2 = sc.nextInt();

        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String m = sc.next();
            String n = sc.next();
            int res = longestCommonSubsequence(m,n);
            System.out.println(res);
        }
    }
    private static int longestCommonSubsequence(String str1,String str2){
        //dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for(int i = 1;i <= str1.length();i++){
            for(int j = 1;j <= str2.length();j++){
                if(str1.charAt(i - 1) == str2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
}
